#include <vector>
#include <unordered_map>
using namespace std;
/*
 * @lc app=leetcode.cn id=207 lang=cpp
 *
 * [207] 课程表
 */

// @lc code=start
class Solution {
public:

    // 本质上就是检测有没有出现环, 受否存在拓扑序
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> before;
        for (int i = 0; i < prerequisites.size(); i++) {
            before[prerequisites[i][0]].push_back(prerequisites[i][1]);
        }
        vector<int> used(numCourses, -1);
        for (int i = 0; i < prerequisites.size(); i++) {
            if (!dfs(prerequisites[i][0], used, before)) return false;
        }
        return true;
    }

    int dfs(int x, vector<int> &used, unordered_map<int, vector<int>> & before) {
        if (used[x] >= 0) return used[x];
        if (before[x].size() == 0) return used[x] = 1;
        used[x] = 0; // 表示已经被访问过了
        for (int i: before[x]) {
            if (!dfs(i, used, before)) return used[x] = 0;
        }
        return used[x] = 1;
        
    } 
};
// @lc code=end

